package com.lw.leetcode.dp.b;

/**
 * Created with IntelliJ IDEA.
 * dp
 * 712. 两个字符串的最小ASCII删除和
 *
 * @author liw
 * @version 1.0
 * @date 2022/1/4 21:42
 */
public class MinimumDeleteSum {

    public static void main(String[] args) {
        MinimumDeleteSum test = new MinimumDeleteSum();

        // 231
//        String str1 = "sea";
//        String str2 = "eat";

        // 403
//        String str1 = "delete";
//        String str2 = "leet";

        // 1399
        String str2 = "ccaccjp";
        String str1 = "fwosarcwge";

        int i = test.minimumDeleteSum(str1, str2);
        System.out.println(i);
    }

    public int minimumDeleteSum(String s1, String s2) {
        int l1 = s1.length();
        int l2 = s2.length();
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        int[][] arr = new int[l1 + 1][l2 + 1];
        int[] ints = arr[0];
        for (int i = 1; i <= l2; i++) {
            ints[i] = ints[i - 1] + c2[i - 1];
        }
        for (int i = 1; i <= l1; i++) {
            arr[i][0] = arr[i - 1][0] + c1[i - 1];
        }
        for (int i = 1; i <= l1; i++) {
            for (int j = 1; j <= l2; j++) {
                if (c1[i - 1] == c2[j - 1]) {
                    arr[i][j] = arr[i - 1][j - 1];
                } else {
                    arr[i][j] = Math.min(arr[i - 1][j] + c1[i - 1], arr[i][j - 1] + c2[j - 1]);
                }
            }
        }
        return arr[l1][l2];
    }

}
